package com.example.algorithm.service.impl;

import com.example.algorithm.model.ListNode;
import com.example.algorithm.model.Node;
import com.example.algorithm.service.ArrayListService;
import org.springframework.stereotype.Service;

import java.util.*;

/**
 * 链表
 * @auth Administrator
 * @create @2024/7/21@19:37
 * @decription
 **/
@Service
public class ArrayListServiceImpl implements ArrayListService {
    /**
     *
     * No.22 相交链表
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * 题目数据 保证 整个链式结构中不存在环。
     * @param headA
     * @param headB
     * @return
     * 解法一：哈希集合
     * 解法二：双指针
     *
     */
    @Override
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA!=pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**No.23 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * @param head
     * @return
     * 解法一：迭代
     * 解法二：递归
     */
    @Override
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode cur =head;
        ListNode temp=null;
        ListNode pre=null;
        while (cur!=null){
            // 下一个
            temp = cur.next;
            // 向前指向
            cur.next=pre;
            // 前一个节点指向当前元素
            pre=cur;
            // 当前元素指向下一个元素
            cur=temp;
        }
        return pre;
    }





    /**No.24 回文列表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为
     * 回文链表
     * 。如果是，返回 true ；否则，返回 false 。
     * @param head
     * @return
     * 解法一：双指针(复制数组或者链表)
     * 解法二：递归
     * 解法三：快慢指针
     * 解法四：栈
     *
     */
    @Override
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> tmp = new Stack();
        ListNode first = head;
        ListNode second = head;
        while (first!=null){
            tmp.push(first.val);
            first = first.next;
        }
        while (second!=null){
            if(second.val!=tmp.pop()){
                return false;
            }
            second = second.next;
        }
        return true;
    }

    /**No.25 环形列表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     *
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     * @param head
     * @return
     * 解法一：哈希表
     * 解法二：快慢指针
     *
     *
     */
    @Override
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow==fast) {
                return true;
            }
        }
        return false;
    }


    /**No.26 环形列表II
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     *
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     *
     * 不允许修改 链表。
     * @param head
     * @return
     * 解法一：哈希表
     * 解法二：快慢指针
     *
     *
     */
    @Override
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow==fast) {
                ListNode left = head;
                ListNode right = slow;
                while (left!=right){
                    left = left.next;
                    right=right.next;
                }
                return left;
            }
        }
        return null;
    }

    /**No.27 合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * @param list1
     * @param list2
     * @return
     * 解法一：递归
     * 解法二：迭代
     * 解法三：创建新链表
     *
     */
    @Override
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1==null){
                return list2;
            }else if(list2==null){
                return list1;
            }
             ListNode res = null;
            if (list1.val<list2.val){
                res = list1;
                res.next = mergeTwoLists(list1.next,list2);
            }else{
                res = list2;
                res.next = mergeTwoLists(list1,list2.next);
            }
        return res;
    }

    /**
     * NO.28 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     *
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     *
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * @param l1
     * @param l2
     * @return
     * 解法一：模拟
     * 解法二：末尾补零法
     * 解法三：对齐补零法
     * 解法四：递归
     * 解法五：迭代
     *
     */
    @Override
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode res = new ListNode(0);
      int sum =0;
      ListNode tmp = res;
      while (l1!=null||l2!=null||sum>0){
          if(l1!=null){
              sum+=l1.val;
              l1=l1.next;
          }
          if(l2!=null){
              sum+=l2.val;
              l2=l2.next;
          }
          tmp.next=new ListNode(sum%10);
          tmp = tmp.next;
          sum = sum/10;
      }
        return res.next;
    }

    /**NO.29.删除链表的倒数第 N 个结点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * @param head
     * @param n
     * @return
     * 解法一：计算链表长度
     * 解法二：栈
     * 解法三：双指针
     * 解法四：快慢指针
     * 解法五：借助数组
     *
     */
    @Override
    public ListNode removeNthFromEnd(ListNode head, int n) {
      ListNode res = head;
      ListNode del = head;
      while (head.next!=null){
          if(n<=0){
              del = del.next;
          }
          head = head.next;
          n--;
      }
      if(n==1){
          return res.next;
      }
      del.next = del.next.next;
      return res;
    }

    /**
     *
     No.30 两两交换链表中的节点
     给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * @param head
     * @return
     * 解法一：递归
     * 解法二：迭代
     * 解法三：栈
     */

    @Override
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode res = head.next;
        head.next=swapPairs(res.next);
        res.next = head;
        return res;
    }

    /**No.31 K一个组翻转
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     *
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     * @param head
     * @param k
     * @return
     * 解法一：模拟
     * 解法二：栈
     * 解法三：尾插法
     * 解法四：递归
     * 解法五：借助数组
     *
     *
     */
    @Override
    public ListNode reverseKGroup(ListNode head, int k) {
        /**
         * 先找到节点
         */
        ListNode last= head;
         for(int i=0;i<k;i++){
             if(last==null){
                 return head;
             }
             last = last.next;
         }
        /**
         * 反转
         */
        ListNode pre=null,curr=head;
         while (curr!=last){
             ListNode tmp = curr.next;
             curr.next = pre;
             pre=curr;
             curr=tmp;
         }
         head.next = reverseKGroup(last,k);
        return pre;
    }

    /**
     *No.32随机链表的复制
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     *
     * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
     *
     * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
     *
     * 返回复制链表的头节点。
     *
     * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
     *
     * val：一个表示 Node.val 的整数。
     * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
     * 你的代码 只 接受原链表的头节点 head 作为传入参数。
     * @param head
     * @return
     * 解法一：回溯+哈希表
     * 解法二：迭代+节点拆分
     * 解法三：哈希表
     *
     */
    /**
     * 哈希表
     *
     * 时间复杂度(O(N))
     * 空间复杂度(O(N))
     * @param head
     * @return
     */
    @Override
    public Node copyRandomList(Node head) {
        if(head==null){
            return head;
        }

      Map<Node,Node> tmp = new HashMap<>();
      //复制入map
        Node curr = head;
        while (curr!=null){
            Node newNode = new Node(curr.val);
            tmp.put(curr,newNode);
            curr = curr.next;
        }
        curr = head;
        while (curr!=null){
            tmp.get(curr).next = tmp.get(curr.next);
            tmp.get(curr).random = tmp.get(curr.random);
            curr = curr.next;
        }

      return tmp.get(head);
    }
    /**
     * 哈希表
     *
     * 时间复杂度(O(N))
     * 空间复杂度(O(1))
     * @param head
     * @return
     */
    public Node copyRandomList1(Node head){
        if(head==null){
            return head;
        }
        Node cur =head;
        /**
         * 复制节点
         */
        while (cur!=null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        /**
         * 赋值随机节点
         */
        cur = head;
        while (cur!=null){
            if(cur.random!=null){
                cur.next.random = cur.random.next;
            }
            cur =cur.next.next;
        }
        /**
         * 拆分节点
         */
        cur = head.next;
        Node pre=head,res=head.next;
        while (cur.next!=null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre=pre.next;
            cur =cur.next;
        }
       pre.next=null;
        return res;
    }



    /**No.33 排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * @param head
     * @return
     * 解法一：归并排序(自顶向下，自底向上)
     * 解法二：辅助数组排序
     * 解法三：冒泡，选择，插入,快排，堆排
     *
     *
     */
    @Override
    public ListNode sortList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode tmp = head;
        List<Integer> tmpList = new ArrayList<>();
        while (tmp!=null){
            tmpList.add(tmp.val);
            tmp = tmp.next;
        }
        Collections.sort(tmpList);
        ListNode res = head;
        Iterator<Integer> iterator = tmpList.iterator();
        while (res!=null&&iterator.hasNext()){
            res.val=iterator.next();
            res = res.next;
        }
        return head;
    }

    /**
     * 34.合并 K个升序链表
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     * @param lists
     * @return
     * 解法一：顺序合并
     * 解法二：分治合并
     * 解法三：优先队列合并
     *
     */
    @Override
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }
        List<Integer> tmpList = new ArrayList<>();
        for(ListNode tmp:lists){
            while (tmp!=null){
                tmpList.add(tmp.val);
                tmp = tmp.next;
            }
        }

            Collections.sort(tmpList);
        ListNode res = new ListNode();
        ListNode next = new ListNode();
        res.next= next ;
        Iterator<Integer> iterator = tmpList.iterator();
        while (next!=null&&iterator.hasNext()){
            ListNode newNode = new ListNode(iterator.next());
            next.next =newNode;
            next = next.next;
        }
        return res.next.next;
    }

    /**
     * 图书整理 I
     * 书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。
     * @param head
     * @return
     */
    @Override
    public int[] reverseBookList(ListNode head) {
           Stack<Integer> stack = new Stack<>();
           List<Integer> res = new ArrayList<>();
           while (head!=null){
               stack.push(head.val);
               head = head.next;
           }
           while (!stack.isEmpty()){
               Integer tmp = stack.pop();
               res.add(tmp);
           }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}
